package com.zjw.algorithm.ready1;

import java.util.ArrayList;
import java.util.List;

public class _计算k置位下标的元素和 {

    public static void main(String[] args) {
        System.out.println(new _计算k置位下标的元素和().sumIndicesWithKSetBits(List.of(5, 10, 1, 5, 2), 1));
    }


    public int sumIndicesWithKSetBits2simple(List<Integer> nums, int k){
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (Integer.bitCount(i) == k){
                ans += nums.get(i);
            }
        }

        return ans;
    }
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }

        //0..n-1 满足k位的下标
        int sum = 0;
        //先算出n的二进制，然后通过组合方式算出下标，
        int res = 1;
        int count = 0;
        while (res <= n) {
            res *= 2;
            count++;
        }

        //0..count范围内枚举k，并且校验小于n，即得出下标，排列组合

        List<Integer> indexList = new ArrayList<>();
        int[] record = new int[count];
        for (int i = 0; i < k && i < count; i++) {
            record[i] = 1;
        }
        find(record, 0, indexList);

        for (Integer index : indexList) {
            if (index < n) {
                sum += nums.get(index);
            }
        }

        return sum;
    }

    private void find(int[] record, int position, List<Integer> nums) {
        if (record.length - 1 == position) {
            //calc num
            int number = 0;
            for (int i = 0; i < record.length; i++) {
                number += (int) Math.pow(2, i) * record[i];
            }
            if (nums.contains(number)) {
                return;
            }
            //restore
            nums.add(number);
            return;
        }

        for (int i = position; i < record.length; i++) {

            if (record[position] == record[i] && position != i) {
                continue;
            }

            int temp = record[position];
            record[position] = record[i];
            record[i] = temp;


            find(record, position + 1, nums);

            temp = record[position];
            record[position] = record[i];
            record[i] = temp;
        }
    }
}
